package LC;

/**
 * https://leetcode.com/problems/insertion-sort-list/description/
 * Sort a linked list using insertion sort.
 */
public class LC_147_InsertionSortList_LinkedList_Sort {

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(3);
        head.next.next = new ListNode(2);
        ListNode h1 = Solution.insertionSortList(head);
        ListNode cur = h1;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    static class Solution {
        static ListNode insertionSortList(ListNode head) {
            ListNode root = new ListNode(0);
            root.next = head;
            ListNode p = head;
            ListNode q;
            ListNode r;
            while (p != null && p.next != null) {
                if (p.val <= p.next.val) {
                    p = p.next;
                } else {
                    q = p.next;
                    p.next = q.next;

                    r = root;
                    while (r.next.val <= q.val) r = r.next;

                    q.next = r.next;
                    r.next = q;
                }
            }
            return root.next;
        }
    }

}